package com.test.spring.solution;

/**
 * 二分查找又称折半查找，效率较高的查找方法
 * 折半查找的算法思想是将数列有序化（递增或递减）排序，查找过程中采用跳跃方式查找，即先以有序数列的中点位置为比较对象，
 * 如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一般。
 *
 * 优点：高效的查找方法，可以明显减少比较次数，提高查找效率。比较次数少，查找速度快，平均性能好
 *
 * 要求及缺点：
 * 1.必须采用顺序存储结构，且插入删除困难
 * 2.必须按关键字大小有序排列
 * 3.折半查找方法适用于不经常变动而查找频繁的有序列表
 *
 *  二分算法步骤描述：
 *  1.首先确定整个查找区间的中间位置mid = (left + right) / 2
 *  2.用待查关键字值与中间位置的关键字值进行比较；
 *  若相等，则查找成功，若大于，则在后（右）半个区域继续进行折半查找，若小于，则在前（左）半个区域继续进行折半查找
 *  3.对确定的缩小区域再折半公式，重复上述步骤。
 *  最后，得到结果：要么查找成功，要么查找失败。
 *  折半查找的存储结构采用一维数组存放。
 *
 *  二分查找算法讨论：
 *  优点：ASL < log2n, 即每经过一次比较，查找范围就缩小一半。经log2n次比较就可以完成查找过程
 *  缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。
 *  另外，顺序存储结构的插入、删除操作不便利
 *
 * @Author ll
 * @Date 2017/8/10 16:20
 */
public class BinarySearch {
    /**
     * 二分查找普通循环实现
     * @param arr
     * @param des
     * @return
     */
    public static int binarySearch(int[] arr, int des) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == des) {
                return mid;
            } else if (arr[mid] < des) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 二分查找递归实现
     *
     * 使用递归调用时，若递归层数过多,调用易造成java.lang.StackOverflowError即栈溢出和程序执行过慢
     * 递归实现导致在栈内存的消耗(需要调整Xss参数)和因为创建栈帧和切换的性能开销，影响效率
     *
     * @param arr
     * @param des
     * @param low
     * @param high
     * @return
     */
    public static int binarySearch(int[] arr, int des, int low, int high) {
        int mid = (high - low) / 2 + low;
        if (arr[mid] == des) {
            return mid;
        }
        if (des > arr[mid]) {
            return binarySearch(arr, des, mid + 1, high);
        } else if (des < arr[mid]) {
            return binarySearch(arr, des, low, mid -1);
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        int[] arrList = new int[80000000];
        for (int i = 0; i < arrList.length; i++){
            arrList[i] = i;
        }
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 10, 11,
                15, 16, 17, 20, 21, 22, 23, 24, 25,
                26, 27, 28, 29, 30, 31, 32, 33, 34,
                111, 112, 113, 114, 115, 116, 117, 118,
                119, 120, 121, 125, 126, 127, 220, 221,
                222, 223, 224, 225, 226, 227, 228, 229,
                332, 333, 334, 335, 336, 337, 338, 339,
                442, 443, 444, 445, 446, 447, 448, 449,
                542, 543, 544, 545, 546, 547, 548, 549,
                642, 643, 644, 645, 646, 647, 648, 649,
                742, 743, 744, 745, 746, 747, 748, 749,
                842, 843, 8844, 845, 846, 847, 848, 849,
                942, 943, 944, 945, 946, 947, 948, 949,
                1111, 1112, 1113, 1114, 1115, 116, 1117,
                1118, 1120, 1121, 1125, 1126, 1127, 1128,
                1220, 1222, 1223, 1224, 1225, 1226, 1227};
        long t1 = System.nanoTime();
        int a = binarySearch(arrList, 200);
        long t2 = System.nanoTime() - t1;
        System.out.println(a + "耗时1：" + t2 + "毫微秒");

        long t3 = System.nanoTime();
        int b = binarySearch(arrList, 126,0, arr.length -1);
        long t4 = System.nanoTime() - t3;
        System.out.println(b + "耗时2：" + t4 + "毫微秒");
    }
}
